35 |
您所在的位置：网站首页 › 稀疏矩阵算法 戴维斯 › 35 |
35
|
1. 稀疏矩阵
一个阶数较大的矩阵中的非零元素个数s相对于矩阵元素的总个数 t 很小时，即 srows = 3; t->cols = 4; t->nums = 0; //扫描矩阵中的非零元素 for(i = 0; i < 3; i++) { for(j = 0; j < 4; j++) { //只存非零值，以三元组方式 if(arr[i][j] != 0) { t->data[t->nums].row = i; t->data[t->nums].col = j; t->data[t->nums].d = arr[i][j]; t->nums++; } } } } 算法：将指定位置的元素值赋给变量x：执行x=arr[ i ] [ j ] //将三元组线性表中指定位置的元素值赋值给变量x void arr_Assign(TSMatrix t , int *data , int i , int j) { int k = 0; //i和j是否合法 if(i >= t.rows || j >= t.cols) { return; } //找到指定元素的行下标 while(k < t.nums && i > t.data[k].row) { k++; } //当找到指定元素的行下标后，再找到指定元素的列下标 while (k < t.nums && i == t.data[k].row && j > t.data[k].col) { k++; } //如果指定元素的行和列都相等，说明找到了 if(t.data[k].row == i && t.data[k].col) { *data = t.data[k].d; } else { //说明没找到 *data = 0; } }算法：三元组元素赋值：执行A[ i ] [ j ] = x 1. 将一个非0元素修改为非0值，如A[ 5 ] [ 6 ] = 8 
将矩阵A中第5行，第6列的元素的值改为8，即修改三元组线性表中的数据元素的值。 2.将一个0元素修改为非0值，如A[ 3 ] [ 5 ] = 8 
将矩阵A中第3行，第6列值为0的元素改为8，这时需要在三元组线性表数组中下标为3的位置往后插入一个数据元素 //修改三元组元素中的值：执行A[i][j]=x void arr_Value(TSMatrix *t , int data , int i , int j) { int k = 0; int k1; //指定的行和列是否合法 if(i >= t->rows || j >= t->cols) { return; } //先查找行 while(k < t->nums && i > t->data[k].row) { k++; } //查找列 while(k < t->nums && i == t->data[k].row && j > t->data[k].col) { k++; } //当找到指定位置时直接修改 if(i == t->data[k].row && j == t->data[k].col) { t->data[k].d = data; } else { //如果指定位置不存在，则说明该元素值为0，此时插入 for(k1 = t->nums; k1 >= k; k1--) { t->data[k1+1].col = t->data[k1].col; t->data[k1+1].row = t->data[k1].row; t->data[k1+1].d = t->data[k1].d; } //插入数据 t->data[k].row = i; t->data[k].col = j; t->data[k].d = data; t->nums++; } }输出三元组：从头到尾扫描三元组t,依次输出元素值 void DispMat(TSMatrix *t) { int i; if(t->nums rows , t->cols , t->nums); printf(" ------------------\n"); //输出所有的三元组 for(i = 0; i < t->nums; i++) { printf("\t第%d行\t第%d列\t%d\n" , t->data[i].row , t->data[i].col, t->data[i].d); } } 5. 测试 int main(void) { //通过自定义3行4列的二维数组来表示稀疏矩阵 int arr[3][4] = { {0 , 1 , 0 , 0}, {0 , 0 , 0 , 2}, {3 , 0 , 0 , 4} }; int data = 0; TSMatrix t = {0}; CreatMat(&t , arr); //输出三元组 DispMat(&t); //获取稀疏矩阵指定位置的值,data的值应该为1才对 arr_Assign(t, &data , 0 , 1); printf("---------------\n"); printf("第0行第1列的数据元素值：%d\n\n" , data); printf("----------------\n"); //将稀疏矩阵第0行第0列元素的值设置为1 arr_Value(&t , data , 0 , 0); //输出三元组 DispMat(&t); return 0; }运行结果： 
|
【本文地址】